import heapq


# 法1
# class Solution(object):
#     def bestRotation(self, nums):
#         nums = [index - num for index, num in enumerate(nums)]
#         st = [[num, index] for index, num in enumerate(nums) if num >= 0]
#         ans = len(st)
#         heapq.heapify(st)
#         k = 0
#         left_st = []
#         wait_st = []
#         t = 0
#         n = len(nums)
#         for index in range(n - 1):
#             while st and st[0][0] <= index:
#                 _, id = heapq.heappop(st)
#                 heapq.heappush(wait_st, id)
#             if nums[index] < 0:
#                 add_index = n - 1 + nums[index]
#                 heapq.heappush(left_st, add_index)
#             while left_st and left_st[0] < index:
#                 heapq.heappop(left_st)
#             while wait_st and wait_st[0] <= index:
#                 heapq.heappop(wait_st)
#                 t += 1
#             new_ans = t + len(left_st) + len(st)
#             if new_ans > ans:
#                 ans = new_ans
#                 k = index + 1
#         return k

# 法2差分数组
class Solution(object):
    def bestRotation(self, nums):
        nums = [index - num for index, num in enumerate(nums)]
        n = len(nums)
        diff = [0] * n
        now = 0
        for index in range(n):
            num = nums[index]
            if num >= 0:
                now += 1
                if num < index:
                    diff[num] -= 1
                    diff[index] += 1
            else:
                add_index = n - 1 + nums[index]
                if add_index >= index:
                    diff[index] += 1
                    diff[add_index + 1] -= 1
        k = 0
        ans = now
        for i in range(n):
            now += diff[i]
            if now > ans:
                ans = now
                k = i + 1
        return k


data = Solution()
nums = [1, 3, 0, 2, 4]
print(data.bestRotation(nums))
